CPE 332
Computer Engineering
Mathematics II
Week 7
Part II, Chapter 6
Queuing System Continue
Extra: PRNG
• Single Server, M/M/1
• Kendal Notation
• Applications
Queuing System Case 3: Delay System Limited Server=N; With Unlimited Queue
x
ρ
λ < µ
p ; 0 ≤ x ≤ N
1
−
0
N
1
−
k
!
x
Nρ
ρ
k
−λ
λ
p =
p
x
x
=
+
N
∑
N
e
; 0
ρ
[
P k] =
N
N!( N − ρ)
k
k =
!
t / T
0
s
1
p ; x ≥ N
[
P T ≥
−
t] = e
; T =
k!
s
0
µ
N! N
Arrival Rate = λ
Departure Rate = µ
Customer
System, N Server
Customer
1.
สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที
2.
เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉล่ีย T
3.
ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้สูงสุด N พร ้อมๆกัน
4.
ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.
ระบบนี้เรียก M/M/N หรือ M/M/N/∞ แสดงได ้ด ้วย Simple Markov Model 6.
State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution 0
1
2
N
N+1
∞
p P = p P
i
ij
j
ji
Queuing System Case 3: Delay System Server=1; With Unlimited Queue; M/M/1
λ < µ 1
ρ
−
p =
+1
=1− ρ
0
k
−λ
λ
− ρ
e
1
(
)
[
P k] =
t / Ts
1
x
[
P T ≥
−
t] = e
; T =
k!
s
p = ρ 1
( − ρ)
µ
x
Arrival Rate = λ
Departure Rate = µ
Customer
System, 1 Server
Customer
1.
สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที
2.
เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉล่ีย T
3.
ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้ครั้งละคน
4.
ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.
ระบบนี้เรียก M/M/1 หรือ M/M/1/∞ แสดงได ้ด ้วย Simple Markov Model 6.
State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution 0
1
2
i
j
∞
p P = p P
i
ij
j
ji
λ
µ=1/Ts
S
Arrival = Poisson, λ
Inter Arrival Time = Exponential, 1/λ
Service Rate, µ
Service Time, Ts (1/µ) = Exponential
Queue = FIFO
1 Server
M/M/1
Queue = 0, No Delay
Queue = Delay
0
1
N+1
N+2
X
Server ว่าง Server Busy
1/Ts = service rate
arrival rate
For each server
λ
µ =1/ Ts
State = 0
No Q Delay
Queue Empty
State = 1
Delay
State = x; Queue = infinity
Customer Wait in Q
State = x; x = Q+1
Severe Delay
Queue Overflow (Full)
กรณีที่
Congestion
Queue มีขนาดจํากัด = Q
Packet Lost
Kendal Notation
Kendal Notation
Kendal Notation
• สมมุติตอนแรกว่า Queue มีขนาดไม่จํากัด
• ใช ้ M/M/1 ในการ Model แต่ละ Port ของ Router (หรือ
Switch L3)
• Arrival คือจํานวน Packet ที่เข ้ามาในช่วงเวลาหนึ่ง ปกติ
วัดเป็น pps
• ขนาดของ Packet สมมุติว่าไม่แน่นอน แต่มีการกระจาย
แบบ Exponential
– Service Time ของแต่ละ Packet จะเป็น Exponential ด ้วย ทั้งนี้
ขึ้นอยู่กับค่า Link Speed ของ Output Port
• ค่า Server Utilization เท่ากับอัตราส่วนของ Arrival Rate หารด ้วย Service Rate จะบ่งบอกอัตราส่วนที่
Server จะ Busy และคือ Link Utilization ของ Output Port ด ้วย
ρ = λ / µ
NW and M/M/1
Arrival Rate
Service Rate = 1/Service Time
λ
µ = 1/ Ts
ρ = λ / µ = λ Ts
• Router ได ้รับ Packet เฉลี่ย 8 pps
– ความยาวของ Packet มีการกระจายแบบ Exponential ด ้วยความยาวเฉลี่ย 500 Octet
– Link ที่จะส่งออกไป มีความเร็ว 64 kbps
• 1. Arrival Rate,λ = 8 pps
• 2. ความยาวเฉลี่ยของ Packet = 4000 bit
• 3. ความเร็ว Link = 64 k ดังนั้น Service Time, Ts ของแต่ละ Packet = 4000/64k = 1/16
• 4. Service Rate(µ) = 16 pps
• 5. Server Utilization = 8/16 =0.5 = 50%
• 1. อย่าลืมว่า Packet ที่เข ้ามา ต ้องเป็น
Independent และ Random มันจึงเป็น
Poisson
• 2. ความยาวของ Packet จะสมมุติว่าเป็น
Exponential ดังนั้น Service Time จะเป็น
Exponential ด ้วย แม ้ว่าสมมุติฐานนี้จะไม่
ถูกต ้องนัก
• 3. มี Output Link เดียว คือเป็น Single
Server
• 4. ดังนี้แล ้ว จึงจะเป็น M/M/1
• Utilization บอกอัตราส่วนที่ Server จะ
Busy และสัมพันธ์กับ Probability ที่
Queue จะว่าง
– Probability ที่ Server ว่าง 1 − ρ
• ใน Network คือคือ Probability ที่
Output Link จะ Busy ด ้วย
ρ = λ / µ = λ Ts
• เนื่องจาก Arrival Rate มีการกระจายแบบ
Poisson ดังนั้นถ ้าให ้
λ เป็นอัตราเฉลี่ย
ของ Customer (Packet) ที่เข ้ามาใน
ช่วงเวลา 1 วินาที
– Probability ที่จะมี k customer (Packet) เข ้า
มาในช่วงเวลา T วินาทีจะหาได ้จาก
( T ) k −λ
λ
e T
p( X = k) = p( k) =
k!
−λ T
p( )
0 = e
•
Ts เป็น Service Time เฉลี่ย และ Service Rate หาได ้จาก µ =1/ Ts
• เนื่องจาก Service Time เป็น Random
Variable ที่มีการกระจายแบบ Exponential
ดังนั้น Probability ที่ Service Time จะมี
ค่าน ้อยกว่า T จะเป็น
− T / Ts
p t
( < T ) = 1 − e
• การกระจายของ Customer (State Probability)
สามารถคํานวณได ้จาก Probability ที่ ระบบ จะมี
k Packet อยู่ดังนี้
k
p = p (λ T )
k
0
s
• โดยที่ p0 คือ Probability ที่ ระบบ จะว่าง
p = 1− ρ = 1− λ T
0
s
• ดังนั้น เราได ้
k
k
p = 1
( − λ T )(λ T ) = 1
( − ρ )ρ
k
s
s
• กล่าวคือ การกระจายของ Customer ในระบบ
หรือค่า State Probability จะเป็น Geometric
Distribution
�હ્યસ઼દ્ઘ� Customer હ્વ�����, N
લ઼�
�લ઼�
�હ્યસ઼દ્ઘ�ય઼�શ઼ State, 𝐸𝐸[𝑋𝑋]
จาก 𝑃𝑃 𝑋𝑋 = 𝑥𝑥 = 𝑝𝑝𝑥𝑥 = 1 − 𝜌𝜌 𝜌𝜌𝑥𝑥 เราได ้
𝐸𝐸 𝑋𝑋 = ∑∞
∞
𝑥𝑥=0 𝑥𝑥 𝑝𝑝𝑥𝑥 = (1 − 𝜌𝜌) ∑𝑥𝑥=0 𝑥𝑥𝜌𝜌𝑥𝑥
แต่จาก (CPE231) ∑∞𝑥𝑥=0 𝑥𝑥𝜌𝜌𝑥𝑥−1 = 1
(1−𝜌𝜌)2
ดังนั้น
𝑋𝑋 = 1 − 𝜌𝜌 𝜌𝜌 ∑∞𝑥𝑥=0 𝑥𝑥𝜌𝜌𝑥𝑥−1 = 𝜌𝜌
1−𝜌𝜌
• จาก Geometric Distribution ค่าเฉลี่ย
คือจํานวน Customer เฉลี่ย คือจํานวน
Packet เฉลี่ยในระบบ จะหาได ้จาก
ρ
N = 1− ρ
• ถ ้าคิดเฉพาะจํานวน Customer เฉลี่ยใน
Queue เราจะได ้ ρ
ρ2
N = N − ρ =
− ρ =
Q
1 − ρ
1 − ρ
• สําหรับ Network ค่าเฉลี่ย จํานวน Packet
เฉลี่ยใน ระบบ และใน Queue จะหาได ้จาก
ρ
ρ 2
N =
N =
1 − ρ
Q
1− ρ
• ถ ้าแต่ละ Packet ต ้องใช ้เวลาเฉลี่ยในการ
Service
T
ดังนั้น ค่า
s
Queuing Delay
จะเป็น
ρ T
ρ
W =
s
=
1 − ρ
µ − λ
• แต่ละ Packet ต ้องใช ้เวลาเฉลี่ยในการ
Service
T
ดังนั้น ค่า
s
Queuing Delay
จะเป็น
ρ T
ρ
W =
s
=
1 − ρ
µ − λ
• และเวลาเฉลี่ยทั้งหมดที่ลูกค ้าจะต ้องรอใน
ระบบทั้งหมดจะเป็น
ρ
T = W + T =
+ 1 = 1
s
µ − λ µ µ − λ
• ถ ้า T เป็นเวลาเฉลี่ยที่ลูกค ้าอยู่ในระบบ และ
λ เป็น Arrival Rate ดังนั้นจํานวนลูกค ้า
เฉลี่ยในระบบจะเท่ากับ
N = λ T
N = λ W
Q
สรุป M/M/1
สรุป M/M/1
สรุป M/M/1
M/M/1 Example 1
6 5 4 3 2 1
λ = ?
µ = ?
S
M/M/1 Example 1
M/M/1 Example 1
M/M/1 Example 1
M/M/1 Example 1
M/M/1 Example 2
λ = ?
µ = ?
M/M/1 Example 2
4.ธนาคารต้องจัดท่ีน่ังก่ีท่ี(รวมท่ีน่ังตอนใช้บริการ)เพ่ือจะ
ให้แน่ใจว่าอย่างน้อย 80% ของผู้ท่ีเข้ามาจะได้น่ัง
4.ธนาคารต้องจัดท่ีน่ังก่ีท่ี(รวมท่ีน่ังตอนใช้บริการ)เพ่ือจะ
ให้แน่ใจว่าอย่างน้อย 80% ของผู้ท่ีเข้ามาจะได้น่ัง
𝑥𝑥 = 9
M/M/1 Example 3
M/M/1 Example 3
M/M/1 Example 3
• HW6 Due Monday Noon
– ส่งที่พี่หนึ่งเท่านั้น ก่อนเที่ยง จันทร์ 29 ก.พ.
– ใส่ตะกร ้า หน ้าโต๊ะ Counter อย่าส่งผิดที่
– เฉลยจะประกาศวันถัดไปบน Web
• Next
– Random Number Generator
– Preparation for Midterm Exam
• Random Number and Properties
• Random Number Test
• Pseudo Random Number Generator
• MT Exam Preparation
• Random Number เป็น Set ของตัวเลขที่
สุ่มขึ้นมาแบบอิสระ(Random) และไม่ขึ้นต่อ
กัน (Independent) โดยมีค่าการกระจาย
(Distribution) ของชุดตัวเลข ตามที่
กําหนดแบบใดแบบหนึ่ง
• เลขแต่ละตัวที่สุ่มจะต ้องไม่มีความสัมพันธ์
กัน ทดสอบได ้จากค่า Correlation
શ઼�� Random Number
• Gambling
• Statistical Sampling
• Simulation
• Cryptography
• Computer Games
• Hash Algorithm/Searching Algorithm
• เป็นอุปกรณ์ที่ใช ้เป็นตัวกําเนิดชุดของตัวเลข
Random ที่ต ้องการ
– True Random Number Generator(TRNG)
• ประกอบด ้วยอุปกรณ์ทาง Physic ที่ใช ้กําเนิดตัวเลข
• มักจะได ้จากแหล่งกําเนิดของ Noise ที่เกิดตาม
ธรรมชาติ
– Thermal Noise/Shot Noise/Radioactive
• หรือใช ้ Roulette Wheel
– Pseudo Random Number Generator(PRNG)
• Computational Algorithm จากสมการทาง
คณิตศาสตร์ โดยเริ่มจากตัวเลข “Seed”
• มีคุณสมบติเหมือนกับเป็น Random แต่มี Period และ
สามารถคํานวณล่วงหน ้าตามสมการได ้
PRNG: Pseudo Random Number Generator: Linear Congruential Generator
• เริ่มจาก “Seed”, 𝑋𝑋0 และคํานวณ Series
𝑋𝑋1, 𝑋𝑋2, 𝑋𝑋3, … จากสมการ Recurrence
𝑋𝑋𝑛𝑛+1 = 𝑎𝑎𝑋𝑋𝑛𝑛 + 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑚𝑚
– a, b และ m เป็น Integer ปกติจะมีขนาดใหญ่; จํานวนเลขสูงสุด
ที่ไม่ซํ้ากันจะถูกกําหนดด ้วยค่า Modulus m
• Sequence ที่ได ้จะมีค่าระหว่าง [0,m) หรือ 0 ≤ 𝑋𝑋 < 𝑚𝑚
• Seed 𝑋𝑋0; 0 ≤ 𝑋𝑋0 < 𝑚𝑚
• Multiplier 𝑎𝑎; 0 < 𝑎𝑎 < 𝑚𝑚
• Increment 𝑏𝑏; 0 ≤ 𝑏𝑏 < 𝑚𝑚
• ถ ้า b = 0 เราเรียก Multiplicative Congruential Generator หรือ Lehmer Generator มิฉะนั้นแล ้วเราเรียก Mixed Congruential Generator
– ตัวเลขที่ได ้จะมีการกระจายแบบ Uniform ถ ้าต ้องการการกระจาย
แบบอื่น จะใช ้การ Transformation
– Algorithm นี้เรียก LCG หรือ Linear Congruential Generator เป็นวิธีที่ง่ายในการสร ้าง PRN
• Period มีค่าได ้สูงสุดคือ m เรียก Full
Period
– บางกรณีจะได ้น้อยกว่านั้น ขึ้นอยู่กับการเลือกค่า
‘a’ และในกรณีที่ b=0
• Generator จะมี Full Period ก็ต่อเมื่อ
(Hull-Dobell Theorem)
– 1. b และ m เป็น Relative Prime
– 2. a-1 จะต ้องสามารถหารได ้ด ้วยทุกๆ factor ที่เป็นค่า prime ของ m
– 3. a-1 จะต ้องหารได ้ด ้วย 4 ถ ้า m หารได ้ด ้วย 4
• ส่วนใหญ่จะใช ้ LCG ที่ m มีค่าเป็นกําลังของ
2 ที่นิยมมากสุดคือ 232 และ 264
– MS Visual C++ ใช ้ m=232,
a=214013,b=2531011
– MS Visual Basic 6 ใช ้ m=224,
a=1140671485,b=12820163
ઙ્ખ દ્ભઢ્ઢ��
ઙ્ઘ�
LCG
• มีข ้อดีคือคํานวณได ้ง่าย แต่ให ้ Series ของ
Random Number ที่มีคุณสมบัติพอประมาณ
เท่านั้น เพราะให ้ค่า Serial Correlation สูง
– ไม่เหมาะกับการนําไปใช ้ใน Monte Carlo
Simulation
– ไม่เหมาะกับการนําไปใช ้ใน Cryptography
• สามารถสร ้างได ้จากวงจร Linear Feedback
Shift Register(LFSR)
– ปกติวงจรนี้จะผลิต Stream ของ bit
• ได ้ Uniform Distributed PRNG
• Blum Blum Shub
• Wichmann-Hill
• Multiply with Carry
• Mersenne Twister (นิยมมากสุด)
• Park-Miller
• RC4
• Rule 30
• เพื่อหา Pattern ในชุด หรือ Series ของตัวเลข
– ซึ่งไม่ควรจะมีอยู่ถ ้าชุดตัวเลขเป็น Random และ
Independent อย่างแท ้จริง
• ใช ้ในการทดสอบ และเปรียบเทียบ Algorithm ต่างๆ
ที่ใช ้ผลิต PRNG โดยใช ้พื้นฐานจาก
– Statistical Test ทดสอบจากคุณสมบัติทางสถิติ
• Diehard Tests ประกอบด ้วยชุดของ Test
• TestU01 library ประกอบด ้วย utilities สําหรับ
statistical testing ของ uniform RNG
– Transform ดูคุณสมบัติเมื่อ Transform
• Hadamard Transform(Generalized FT)
– Complexity ความซับซ ้อนของตัวเลข
• Kolmogorov complexity
• เก็บ 35 เปอร์เซ็นต์
• ไม่มีการ Make Up
• สอบ 3 ชั่วโมง บทที่ 1-6
– Monday 7 March; 13:30 – 16:30
• ต ้องใช ้เครื่องคิดเลข
– รุ่นตามที่คณะประกาศเท่านั้น ห ้ามใช ้อุปกรณ์อื่นๆ
• สมการที่สําคัญจะให ้มา ไม่ต ้องจํา
• 6 ข้อ บทละ 1 ข้อ รวม 6 ข้อ เลือกทํา 5 ข้อ
– 5 ข้อ 50 คะแนน คิดเป็น 35 %
สมการที่ให้
ในการสอบ MT
દ્ધય઼�
���મ઼દ્ભ��
• Chapter 1: Vector
– Magnitude/Direction/Unit Vector
– Direction Cosine
– Component Vector/Position Vector
– Dot/Cross Product and Properties
– Equation of Line and Plane, Angle of Vectors
• Chapter 2: Matrices
– Types of Matrices, Minor, Cofactor, Diagonal
– Determinant by Expansion
– Inverse of Matrix
– Rank/Reduced Matrix (Process of Elimination)
– Homogeneous/Non Homogeneous Linear Eq.
દ્ધય઼�
���મ઼દ્ભ��
• Chapter 3: Eigen Value/Vector/Diag
– Eigenvalues
– Eigenvectors
– Diagonalization
– Symmetric/Orthogonal Matrix
• Chapter 4: Probability
– Conditional Probability/Bayes Rule
– Random Variable
– CDF/PDF/PMF; Poisson/Exponential Distribution
– Expectation Concept
– Mean, Mean Square, Variance
– Joint Random Variable, Correlation/Covariance
દ્ધય઼�
���મ઼દ્ભ��
• Chapter 5: Random Process
– Stationary/Ergodic
– Autocorrelation/Cross Correlation
– Counting/Poisson Process/Birth and Death Process
– MarKov Model; Global Balanced Equation
– Simple MarKov Model; Detail Balanced Equation
• Chapter 6: Queuing System
– M/M/1 Concept
– Arrival Rate/Inter Arrival Time
– Departure Rate/Service Time
– Utilization, P[X=k], P[X<=k]
– Average Customer(System/Q), Time(System/Q)